package medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/12/20 20:03
 */
public class No57_插入区间 {
    public static void main(String[] args) {
        Solution57 solution57 = new Solution57();
        int[][] intervals = new int[][]{
                {2, 5},
                {8, 12}
        };
        int[] newInterval = new int[]{6, 9};
        int[][] insert = solution57.insert(intervals, newInterval);
        System.out.println(insert);
    }
}

class Solution57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        //一次遍历
        //定义list存放结果
        List<int[]> list = new ArrayList<>();
        int a = newInterval[0];
        int b = newInterval[1];
        //红色区间可加:true false
        boolean addOpen = true;
        for (int[] interval : intervals) {
            int x = interval[0];
            int y = interval[1];
            //开始判断interval跟newInterval的关系

            if (b < x) {
                //插入区间在左侧
                //插入红色区间,同时再插入当前元素
                //注意,下一次循环,则不能插入红色区间
                if (addOpen) {
                    //红色插入
                    list.add(new int[]{a, b});
                    addOpen = false;
                }
                list.add(interval);
            } else if (y < a) {
                //插入区间在右侧
                list.add(interval);
            } else {
                //把插入的区间合并成大区间!
                a = Math.min(a, interval[0]);
                b = Math.max(b, interval[1]);
            } 
        }

        if (addOpen) {
            //则加
            list.add(new int[]{a, b});
        }
        
        
        //list搞成数组
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i][0] = list.get(i)[0];
            res[i][1] = list.get(i)[1];
        }
        return res;
    }
}



    //public int[][] insert(int[][] intervals, int[] newInterval) {
    //    //强行硬写,参照56,暴力走起,玩具也!!!!!
    //    //数组搞成list
    //    List<List<Integer>> listData = new ArrayList<>();
    //    for (int[] interval : intervals) {
    //        List<Integer> data = new ArrayList<>();
    //        data.add(interval[0]);
    //        data.add(interval[1]);
    //        listData.add(data);
    //    }
    //    
    //    //newInterval扔
    //    listData.add(new ArrayList<>(Arrays.asList(newInterval[0], newInterval[1])));
    //
    //    //listData API排序
    //    //搬运代码
    //    listData.sort(new Comparator<List<Integer>>() {
    //        @Override
    //        public int compare(List<Integer> o1, List<Integer> o2) {
    //            //[2,5][8,12]
    //            if (o1.get(0) > o2.get(0)) {
    //                return 1;
    //            } else if (o1.get(0) < o2.get(0)) {
    //                return -1;
    //            } else if (o1.get(0) == o2.get(0)) {
    //                return 0;
    //            }else {
    //                return o1.get(1) < o2.get(1) ? -1 : 1;
    //            } 
    //        }
    //    });
    //    
    //    //继续搬运代码,list合并
    //    
    //    //开始合并
    //    List<List<Integer>> res = new ArrayList<>();
    //    for (int i = 0; i < listData.size(); i++) {
    //        mergeList(res, listData.get(i));
    //    }
    //    
    //    //搞回数组
    //    int[][] resInts = new int[res.size()][2];
    //    for (int i = 0; i < res.size(); i++) {
    //        resInts[i][0] = res.get(i).get(0);
    //        resInts[i][1] = res.get(i).get(1);
    //    }
    //
    //    return resInts;
    //}
    //
    ////合并list方法
    //public void mergeList(List<List<Integer>> res, List<Integer> data) {
    //
    //    if (res.size() == 0) {
    //        res.add(data);
    //        return;
    //    }
    //    
    //    //将data合并进res
    //    
    //    //获取x,y
    //    int x = res.get(res.size() - 1).get(0);
    //    int y = res.get(res.size() - 1).get(1);
    //
    //    int a = data.get(0);
    //    int b = data.get(1);
    //    
    //    //按规律进行合并
    //    if (a >= x && a <= y && b > y) {
    //        //(x,b)
    //        res.remove(res.size() - 1);
    //        data.clear();
    //        data.add(x);
    //        data.add(b);
    //        res.add(data);
    //    } else if (a >= x && a <= y && b <= y) {
    //        //(x,y)
    //        res.remove(res.size() - 1);
    //        data.clear();
    //        data.add(x);
    //        data.add(y);
    //        res.add(data);
    //    } else if (a > y) {
    //        res.add(data);
    //    }
    //    
    //}




